package LeetCode.month01.day14;

import java.util.Enumeration;
import java.util.HashMap;

public class No287 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,1};
        System.out.println(findDuplicate(nums));
    }
    public static int findDuplicate(int[] nums) {
        //快慢指针
//        int slow = 0,fast = 0;
//        do{
//            slow=nums[slow];
//            fast = nums[nums[fast]];
//        }while(fast != slow);
//        slow = 0;
//        while(slow!=fast){
//            slow=nums[slow];
//            fast = nums[fast];
//        }
//        return slow;



        int left=0,right=nums.length-1;
        int n = nums.length;
        int ans = -1;
        while(left<=right){
            int cnt = 0;
            int mid = left+(right-left)/2;
            for (int i = 0; i < n; i++) {
                if(nums[i]<=mid) cnt++;
            }
            if(cnt<=mid) left = mid+1;
            else {
                right = mid-1;
                ans = mid;
            }
        }
        return ans;
    }
}
